#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <stack>
#define random(a,b) (rand()%(b-a)+a)

using namespace std;
struct ListNode;
ListNode* intersect(ListNode* p1, ListNode* p2, int, int);
ListNode* createList(ListNode* p, vector<int> &);
int getLength(ListNode *head);
int res_size = 0;
int flag = 0;

struct ListNode {
    int value;
    ListNode *next;
    ListNode() : value(0), next(nullptr) {}
    ListNode(int x) : value(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : value(x), next(next) {}
    };

int main() {
    srand((int)time(0));
    vector<int> nums1 = {2,4,9,10,12,15,18,21};
    vector<int> nums2 = {1,3,5,10,15,18};
    int size1 = nums1.size();
    int size2 = nums2.size();
    ListNode *p1 = new ListNode();
    ListNode *p2 = new ListNode();
    p1 = createList(p1, nums1);
    cout << " " << endl;
    p2 = createList(p2, nums2);
    cout << " " << endl;
    ListNode *result = intersect(p1, p2, size1, size2);
    result = result->next;
    for (int i = 0; i < res_size; i++)
    {
        cout << result->value << endl;
        result = result->next;
    }
    return 0;
    }

ListNode* createList(ListNode* p, vector<int> &nums) {
	p->value = 1;
	ListNode* pNode = p;
	for (int i = 0; i < nums.size(); i++)
	{
		ListNode* pNew = new ListNode();
		pNew->value = nums[i];
		cout << pNew->value << endl;
		pNew->next = nullptr;
		pNode->next = pNew;
		pNode = pNew;
	}
	return p;
}

ListNode* intersect(ListNode* p1, ListNode* p2, int size1, int size2) {
    stack<int> nums;
    ListNode* head = new ListNode();
    ListNode* p = head;
    ListNode* temp = ((size1 < size2) ? p1->next : p2->next);
    ListNode* temp1 = ((size1 >= size2) ? p1->next : p2->next);
    for (int i = 0; i < ((size1 < size2) ? size1 : size2); i++) {
        temp1 = ((size1 >= size2) ? p1->next : p2->next);
        nums.push(temp->value);
        for (int j = 0; j < ((size1 >= size2) ? size1 : size2); j++) {
            if (temp1->value == nums.top()) {
                ListNode* pNew = new ListNode();
                pNew->value = nums.top();
                p->next = pNew;
                p = pNew;
                res_size++;
                nums.pop();
                break;
                }
                temp1 = temp1->next;
            }
            temp = temp->next;
        }
    return head;
    }

int getLength(ListNode *head) {
     if (head = NULL)
        return 0;
     int length = 0;
     ListNode *temp = head;
     while (temp != nullptr){
        length++;
        temp = temp->next;
     }
     return length;
}
